# -*- coding: utf-8 -*-

#-----------------------------------------------------------------------------------------------------------------------
#class Solution(object):
    #def increasingTriplet(self, nums):
        #"""
        #:type nums: List[int]
        #:rtype: bool
        #"""
        #res = [float('inf'), float('inf')]
        #i = 0
        ## 思路是把遇到的最小的值存下来,遇到比最小值大的都放到res[1]里面,只要遇到了n > res[1]的就是满足了3个递增
        #for n in nums:
            #if n > res[1]:
                #return True
            #if n <= res[0]:
                #res[0] = n
            ## 这个else 是因为 n > res[0]
            #else:
                #res[1] = n
        #return False
#s =  [2,1,5,3,2,6]
#sss = Solution()
#qqq = sss.increasingTriplet(s)
#print(qqq)
#-----------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------
# 写的真好,每次看别人的代码都会觉得耳目一新,还记得当时看机器学习的代码的思路,简直太新奇,就是忘得快,只能记住一部分
#class Solution(object):
    #def longestPalindrome(self, s):
        #"""
        #:type s: str
        #:rtype: str
        #"""
        #n = len(s)
        #maxL, maxR, max = 0, 0, 0
        #for i in range(n):
            ## 长度为偶数的回文字符串
            #start = i      
            #end = i + 1
            ## 首先保证不超过索引限制,例如不能出现end>最后一个,下个while同
            #while start >= 0 and end < n:
                #if s[start] == s[end]:
                    ## 防止小的把历史中大的子回文字符串冲掉
                    #if end - start + 1 > max:
                        #max = end - start + 1
                        #maxL = start
                        #maxR = end
                    ## 例如 a bb a
                    ## start-=1 就会再次判断a和下一个是否相等,直到找出最大的
                    #start -= 1
                    #end += 1
                #else:
                    #break
            ## 长度为奇数的回文子串
            #start = i - 1
            #end = i + 1
            #while start >= 0 and end < n:
                #if s[start] == s[end]:
                    #if end - start + 1 > max:
                        #max = end - start + 1
                        #maxL = start
                        #maxR = end
                    #start -= 1
                    #end += 1
                #else:
                    #break
        #return s[maxL:maxR+1]
    
## leetcode中耗时最短
#class Solution:
    #def longestPalindrome(self, s):
        #"""
        #:type s: str
        #:rtype: str
        #"""
        #if len(s)<2 or s==s[::-1]:
            #return s
        #n=len(s)
        #start,maxlen=0,1
        #for i in range(n):
            #odd =s[i-maxlen-1:i+1] #len(odd)=maxlen+2
            #even=s[i-maxlen:i+1]    #len(even)=maxlen+1
            #if i-maxlen-1>=0 and odd==odd[::-1]:
                #start=i-maxlen-1
                #maxlen+=2
                #continue
            #if i-maxlen>=0 and even==even[::-1]:
                #start=i-maxlen
                #maxlen+=1
        #return s[start:start+maxlen]
#s =  "abbacc"
#sss = Solution()
#qqq = sss.longestPalindrome(s)
#print(qqq)
#-----------------------------------------------------------------------------------------------------------------------


#-----------------------------------------------------------------------------------------------------------------------
# # 这个没太理解
#class Solution(object):
    #def lengthOfLongestSubstring(self, s):
        #"""
        #:type s: str
        #:rtype: int
        #"""
        ## 存储历史循环中最长的子串长度
        #max_len = 0
        ## 判断传入的字符串是否为空
        #if s is None or len(s) == 0:
            #return max_len
        ## 定义一个字典，存储不重复的字符和字符所在的下标
        #str_dict = {}
        ## 存储每次循环中最长的子串长度
        #one_max = 0
        ## 记录最近重复字符所在的位置+1
        #start = 0
        #for i in range(len(s)):
            ## 判断当前字符是否在字典中和当前字符的下标是否大于等于最近重复字符的所在位置
            #if s[i] in str_dict and str_dict[s[i]] >= start:
                ## 记录当前字符的值+1
                #start = str_dict[s[i]] + 1
            ## 在此次循环中，最大的不重复子串的长度
            #one_max = i - start + 1
            ## 把当前位置覆盖字典中的位置
            #str_dict[s[i]] = i
            ## 比较此次循环的最大不重复子串长度和历史循环最大不重复子串长度
            #max_len = max(max_len, one_max)
        #return max_len
#s = "dvdf"
#sss = Solution()
#qqq = sss.lengthOfLongestSubstring(s)
#print(qqq)
#-----------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------
#class Solution:
    #def groupAnagrams(self, strs):
        #"""
        #:type strs: List[str]
        #:rtype: List[List[str]]
        #"""
        #思路:排序后利用字典的get方法
        #d = {}
        #for x in strs:
            #key = tuple(sorted(x))
            #d[key] = d.get(key,[]) + [x]
        #return list(d.values())
#strs = ["eat", "tea", "tan", "ate", "nat", "bat"]  
#sss = Solution()
#qqq = sss.groupAnagrams(strs)
#print(qqq)
#-----------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------
# class Solution(object):
#     def setZeroes(self, matrix):
#         """
#         :type matrix: List[List[int]]
#         :rtype: void Do not return anything, modify matrix in-place instead.
#         """
#         # 思路遍历遇到0,记录行,列,把对应的行列置0
#         n_row = len(matrix)
#         n_col = len(matrix[0])
#         row_zero = []
#         col_zero = []
#         for i in range(n_row):
#             for j in range(n_col):
#                 if matrix[i][j] == 0:
#                     row_zero.append(i)
#                     col_zero.append(j) 
#         for i in row_zero:
#             for j in range(n_col):
#                 matrix[i][j] = 0
#         for i in range(n_row):
#             for j in col_zero:
#                 matrix[i][j] = 0
#         return matrix
# matrix = [[1,1,1],
#         [1,0,1],
#         [1,1,1]]    
# sss = Solution()
# qqq = sss.setZeroes(matrix)
#-----------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------
# class Solution:
#     def setZeroes(self, matrix):
#         """
#         :type matrix: List[List[int]]
#         :rtype: void Do not return anything, modify matrix in-place instead.
#         """
#         nrow = len(matrix)
#         if nrow < 1:
#             return
#         else:
#             ncol = len(matrix[0])
#         row_mask, col_mask = [], []
#         for i in range(nrow):
#             for j in range(ncol):
#                 if matrix[i][j] == 0:
#                     row_mask.append(i)
#                     col_mask.append(j)
                    
#         def set_row_zero(r, matrix, ncol):
#             for j in range(ncol):
#                 matrix[r][j] = 0
        
#         def set_col_zero(c, matrix, nrow):
#             for i in range(nrow):
#                 matrix[i][c] = 0   
                
#         for r in row_mask:
#             set_row_zero(r, matrix, ncol)
            
#         for c in col_mask:
#             set_col_zero(c, matrix, nrow)
        
#         return
                    
# matrix = [[1,1,1],
#         [1,0,1],
#         [1,1,1]]    
# sss = Solution()
# qqq = sss.setZeroes(matrix)
#-----------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------
# class Solution:
    # def threeSum(self, nums):
        # """
        # :type nums: List[int]
        # :rtype: List[List[int]]
        # """
        # # 思路:把正数负数分类,
        # # 1.三个0的情况
        # # 2.取一正一负,第三个数 = 0-正-负,这个数(一定是两种情况之一)是否在俩数中间或者是其中的一个数
        # import collections        
        # d = collections.Counter(nums)
        # nums_keys = d.keys()               
        # pos, neg = [],[]       
        # for p in nums_keys:
            # if p >= 0:
                # pos.append(p)
            # else:
                # neg.append(p)                
        # r = []       
        # if d.get(0,0) > 2:
            # r.append([0,0,0])
        
        # for i in neg:
            # for j in pos:
                # tar = - i - j
                # if tar in nums_keys:
                    # if i< tar < j:
                        # r.append([i,tar,j])
                    # # 这个数(一定是两种情况之一)是否在俩数中间或者是其中的一个数
                    # elif (j==tar or i == tar) and d[tar]>1: 
                        # r.append([i,tar,j])
        # return r
# nums = [-1, 0, 1, 2, -1, -4]        
# sss = Solution()
# qqq = sss.threeSum(nums)
#-----------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------
# class Solution:
    # def threeSum(self, nums):
        # """
        # :type nums: List[int]
        # :rtype: List[List[int]]
        # """  
        # # 整体的思路是先排序,然后从0开始遍历
        # # 遍历方法:用第nums[i],nums[i+1],nums[-1]相加,
        # #如果s>0,说明最后一个数太大了,就减小一个nums[-2],否则就是太小了,就nums[i+2]
        # # 如果s=0,加到list中,并同时左右各移动一位(下一轮运算,为什么左右都要移动,因为目前的符合条件,单移动一边,
        # # 一定会导致要么一定不符合s=0,要么就是重复的),
        # nums.sort()#排序
        # res =[]
        # i = 0
        # for i in range(len(nums)):
            # if i == 0 or nums[i]>nums[i-1]:
                # l = i+1
                # r = len(nums)-1
                # while l < r:
                    # s = nums[i] + nums[l] +nums[r]
                    # if s ==0:
                        # res.append([nums[i],nums[l],nums[r]])
                        # l +=1
                        # r -=1
                        # while l < r and nums[l] == nums[l-1]:#避免相同值
                            # l += 1
                        # while r > l and nums[r] == nums[r+1]:
                            # r -= 1
                    # elif s>0:     # 说明最后一个数太大了,就减小一个nums[-2]
                        # r -=1
                    # else :
                        # l +=1
        # return res      
# nums = [-1, 0, 1, 2, -1, -4]        
# sss = Solution()
# qqq = sss.threeSum(nums)
#-----------------------------------------------------------------------------------------------------------------------
